Rodzynki
Limit pamięci: 128 MB
Słynna producent czekolady z Plovdiv, Bonny, musi pociąć tabliczkę czekolady
z rodzynkami.
Czekolada jest prostokątem składającym się z jednakowych, kwadratowych kawałków.
Kawałki są ułożone równolegle do krawędzi czekolady w rzędach i
kolumnach, co daje łącznie kawałków.
Każdy z kawałków zawiera pewną dodatnią liczbę rodzynek, a żadne rodzynki
nie leżą na liniach oddzielających kawałki.
Początkowo czekolada jest w całości.
Bonny chce ją ciąć na coraz mniejsze fragmenty, aż w końcu otrzyma czekoladę
podzieloną na pojedynczych kawałków.
Ponieważ Bonny jest bardzo zajęta, do pomocy przy cięciu potrzebuje pomocy swego
asystenta, Chytrego Piotra.
Piotr tnie czekoladę po prostych, od brzegu do brzegu, i oczekuje zapłaty
za każde wykonane cięcie.
Bonny chwilowo nie posiada pieniędzy, ma za to sporo rodzynek, które nie
zostały użyte, więc oferuje Piotrowi zapłatę w rodzynkach.
Chytry Piotr zgadza się, ale pod warunkiem, że za każde przecięcie fragmentu
czekolady na dwa mniejsze dostanie tyle rodzynek, ile jest ich łącznie
w tym fragmencie.
Bonny chciałaby dać Piotrowi jak najmniej rodzynek.
Wie dokładnie, ile rodzynek jest w każdym z kawałków.
Może też zadecydować o kolejności, w której będzie podawać Piotrowi fragmenty
czekolady, a także kazać mu wykonywać cięcia w konkretnym kierunku
(w pionie lub poziomie) i wzdłuż konkretnej linii.
Pomóż Bonny znaleźć taki sposób cięcia czekolady na pojedyncze kawałki,
żeby zapłaciła Chytremu Piotrowi jak najmniej rodzynek.
Zadanie
Napisz program, który mając dane liczby rodzynek w poszczególnych kawałkach
czekolady, wyznaczy minimalną liczbę rodzynek, które Bonny będzie musiała
oddać Chytremu Piotrowi.
Ograniczenia
- liczby kawałków na każdym z boków czekolady
- liczba rodzynek w kawałku czekolady w -tym wierszu i -tej kolumnie
Wejście
Twój program powinien wczytać ze standardowego wejścia następujące dane:
- Pierwszy wiersz zawiera liczby całkowite i , oddzielone
pojedynczym odstępem.
- Kolejne wierszy zawiera informacje o rozmieszczeniu rodzynek
w poszczególnych ka\-wał\-kach czekolady.
-ty z tych wierszy opisuje -ty wiersz czekolady
i zawiera liczb całkowitych pooddzielanych pojedynczymi odstępami.
Liczby te opisują kawałki w danym wierszu, od lewej do prawej.
-ta liczba w -tym wierszu (spośród wierszy, o których mowa)
to liczba rodzynek, które znajdują się w kawałku czekolady w -tym
wierszu i -tej kolumnie.
Wyjście
Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający
jedną liczbę całkowitą: minimalną liczbę rodzynek, które Bonny musi oddać
Chytremu Piotrowi.
Ocenianie
W testach wartych łącznie 25 punktów i nie przekroczą 7.
Przykład
Dla danych wejściowych:
2 3
2 7 5
1 9 5
poprawną odpowiedzią jest:
77
Wyjaśnienie do przykładu: oto jeden z możliwych sposobów (spośród wielu) osiągnięcia kosztu 77 rodzynek.
Pierwszym cięciem, o które prosi Piotra Bonny, jest oddzielenie trzeciej kolumny
od reszty czekolady.
Bonny płaci za to 29 rodzynek.
Następnie, Bonny daje Piotrowi mniejszy z fragmentów - ten złożony z dwóch
kawałków zawierających po 5 rodzynek - a Piotr przecina go na pół za 10 rodzynek.
Później Bonny daje Piotrowi największy z pozostałych fragmentów - ten zawierający
kawałki z 2, 7, 1 oraz 9 rodzynkami.
Bonny prosi o poziome cięcie, które oddzieli pierwszy wiersz od drugiego,
i płaci 19 rodzynek.
Następnie, Bonny daje Piotrowi lewy górny fragment, płacąc 9 rodzynek.
W końcu Bonny prosi Piotra o podzielenie lewego dolnego fragmentu za 10
rodzynek.
Całkowity koszt, jaki ponosi Bonny, to rodzynek.
Żaden inny schemat cięć nie podzieli tej czekolady na 6 kawałków mniejszym kosztem.